/*
 * @lc app=leetcode.cn id=1175 lang=cpp
 *
 * [1175] 质数排列
 */

// @lc code=start
class Solution {
public:
    int mod = 1e9 + 7;
    int isPrime(int n) {
        if (n <= 1) return 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return 0;
        }
        return 1;
    }
    long factorial(int n) {
        long res = 1;
        while (n) {
            res = res % mod;
            res = res * n;
            n--;
        }
        return res;
    }
    int numPrimeArrangements(int n) {
        int primes = 0, ans = 1;
        for (int i = 1; i <= n; i++) {
            if (isPrime(i)) primes++;
        }
        int nPrimes = n - primes;

        ans = (int)(factorial(primes) * factorial(nPrimes) % mod);

        return ans;
    }
};
// @lc code=end
